/*
 * @Author: szx
 * @Date: 2022-03-12 14:30:47
 * @LastEditTime: 2022-03-12 15:18:15
 * @Description:
 * @FilePath: \leetcode\1100-1199\1155\1155.js
 */
/**
 * @param {number} n
 * @param {number} k
 * @param {number} target
 * @return {number}
 */
var numRollsToTarget = function (n, k, target) {
    let res = 0;
    const backtrace = (sum, index, num) => {
        if (num > n || sum > target) return;
        if (sum == target) {
            res++;
            return;
        }
        for (let i = index; i <= k; i++) {
            backtrace(sum + i, index, num + 1);
        }
    };
    backtrace(0, 1, 0);
    return res;
};

var numRollsToTarget = function (n, k, target) {
    const dp = new Array(n + 1).fill(0).map(() => new Array(target + 1).fill(0));
    for (let i = 1; i <= Math.min(target, k); i++) dp[1][i] = 1;
    for (let i = 2; i <= n; i++) {
        for (let j = i; j <= target; j++) {
            for (let m = 1; m < j && m <= k; m++) {
                dp[i][j] = (dp[i][j] + dp[i - 1][j - m]) % (1e9 + 7);
            }
        }
    }
    return dp[n][target];
};



// console.log(numRollsToTarget(1, 6, 3));
console.log(numRollsToTarget(2, 6, 7));
// console.log(numRollsToTarget(30, 30, 500));
